package org.shj.algorithm.string;

/**
 * 字符串匹配问题： 给定文本 text 和模式串 pattern。从文本串中找出模式串第一次出现的位置
 * 暴力方法: 外层循环文本串的每个字符，内层循环模式串的每个字符，一一比较。当不相等时，外层循环
 *          起始位置增1，内层循环起始位置归0
 * 以文本串 A= abcabcabx 和模式串 B= abcabx 为例, i 为文本串的字符位置，j 为模式串的字符位置，第一位均为0
 * (1)  a b c a b c a b x
 *      a b c a b x
 *   当 i = 5 , j = 5 时， A[5]=c 与 B[5]=x 不相等，此时把 i 回溯到 1 的位置，j 回溯到 0 的位置
 * (2) A[1]=b 与 B[0]=a 不相等，i 变成 2, j 变成 0
 * (3) A[2]=c 与 B[0]=a 不相等，i 变成 3, j 变成 0，
 * (4) 此时比较位置如下
 *     a b c a b c a b x
 *           a b c a b x
 * (5) A[3]=a 与 B[0]=a 相等, i 和 j 同时加 1, 再进行比较
 * (6) A[4]=b 与 B[1]=b 相等, i 和 j 同时加 1, 再进行比较
 * (7) A[5]=c 与 B[2]=c 相等, i 和 j 同时加 1, 再进行比较
 * (8) 重复上面的步骤，可以得出最后结果
 *
 * 在第(2)步时，我们发现，在(1)中，已经知道 B[1]=b=A[1] 了，而且 B[0]=a 与 B[1]=b 不相等，我们自然知道
 * B[0] != A[1]，这一步比较其实可以省略。同理，第(3)步 A[2] 与 B[0] 的比较也可以省略。
 * 在第(5)步时, 我们发现，在(1)中，已经知道 B[3]=a=A[3] 了,且 B[0]=B[3]，所以我们知道 A[3]=B[0]，这一
 * 步的比较也是可以省略的。同理，第（6）步也可以省略，应该直接进行第（7）步。
 *
 * 使用不同的模式串分析暴力方法的步骤，我们可以发现，每当两个字符不相等时，i 的值其实是可以不回溯的，j 的值
 * 在模式串有些相似的情况下，也不必完全回溯成 0。这就是 KMP 算法的思想。那么 j 值回溯到哪个位置的规律是什么
 * 呢？我们发现，当模式串中某个位置的字符与文本串不相等时，j 需要回溯，回溯的位置取决于模式串中以第 0 个字符
 * 开始和以第 j - 1 个字符结束的字符串的最大的相似度。其回溯的位置只跟模式串有关，跟文本串无关。
 * 如在(1)中，A[5]=c 与 B[5]=x 不相等时，i = 5 保持不变，j 应该回溯到第(7)步中 j 的位置，j 应为 2，我们
 * 可以看出回溯前 j=5，在这个字符之前的字符串是 abcab, 以第 0 个字符串开始的字符串 ab 和以第 j - 1 字符串
 * 结尾的字符串 ab 是 abcab 中最长的相似字符串，其长度是 2，而 2 就是我们要回溯的位置。如果没有相似字符串，
 * 则 j 只能回溯到 0 的位置。
 * 因此，我们需要先求出模式串中每一个字符当其与文本串不匹配时，j 应该回溯的位置。
 *
 * 注意：KMP 算法只在模式串相似度较高的情况下才体现出优势。
 *
 * @author Shen Huang Jian
 * @date 2019-03-25 12:17
 */
public class KMP {

    public static void main(String[] args){
        String pattern = "abcabx"; // next[] 应该是 0, 0, 0, 0, 1, 2
        //String pattern = "ababaaaba"; // next[] 应该是 0, 0, 0, 1, 2, 3, 1, 1, 2
        indexKMP("abcababcabxa", pattern);
    }

    private static void indexKMP(String text, String pattern){
        //int[] next = calcNextBad(pattern);
        //int[] next = calcNextNice(pattern);
        int[] next = calcNextBetter(pattern);
        int i = 0, j = 0;
        while(i < text.length() && j < pattern.length()){
            if(text.charAt(i) == pattern.charAt(j)){
                i++;
                j++;
            }else{
                if(j == 0){//如果第一位不相等了，i 需要加1，否则某些情况会死循环
                    i++;
                }
                // 不相等时，只有 j 回溯
                j = next[j];
            }
        }

        int index = j >= pattern.length() ? (i - pattern.length()): -1;

        System.out.println(index);
    }

    private static int[] calcNextNice(String pattern){
        int[] next = new int[pattern.length()];
        if(pattern.length() <= 2){
            return next;
        }
        next[0] = 0; //第一个(第0位)总是 0
        next[1] = 0; //第二个总是 0
        int i = 2, j = 0;
        int loop = 0;
        while(i < next.length){
            loop++;
            if(pattern.charAt(i - 1) == pattern.charAt(j)){
                j++;
                next[i] = j;
                i++;
            }else{
                if(j == 0){//表示只是比较第一个字符时就不相等时，i 需要往后移一位
                    i++;
                }
                j = 0;
            }
        }

        System.out.println("loop is: " + loop);

        //打印
        printNext(next);
        return next;
    }

    /**
     * 此方法比较好理解，但是循环次数明显比上面的方法多很多。
     * @param pattern
     * @return
     */
    private static int[] calcNextBad(String pattern){
        int[] next = new int[pattern.length()];
        next[0] = 0; //第一个总是 0
        next[1] = 0; //第二个总是 0

        int loop = 0;
        for(int i = 2; i < pattern.length(); i++){
            int max = 0;
            for(int k = 1; k < i; k++){
                loop++;
                String preKChar = pattern.substring(0, k);
                String suffixKChar = pattern.substring(i - k, i);
                //前面 K 个字符和最后 K 个字符相等
                if(preKChar.equals(suffixKChar)){
                    max = k;
                }
            }
            next[i] = max;
        }
        System.out.println("loop is: " + loop);

        printNext(next);
        return next;
    }

    /**
     * KMP 算法的改进：
     * 假设文本串为 A= aaaabcde, 模式串为 B=aaaaax
     * 则：next[] = [0, 0, 1, 2, 3, 4]
     * 当比较到 A[4]=b，B[4]=a 时，j 回溯到 next[4]=3 的位置，此位置还是 a，与 B[4] 相等，
     * 因此可以知道与 A[4] 也不相等，需要继续回溯到 next[3]=2 的位置。我们发现 B[2]=B[3],
     * 所以也不会与 A[4] 相等...... 可以发现有些比较还是可以省略的。也就是说，j 的位置的字符
     * 如果与需要回溯到的位置的字符相等的话，其实可以直接回溯到回溯的位置对应需要回溯到的位置。
     *
     * @param pattern
     * @return
     */
    private static int[] calcNextBetter(String pattern){
        int[] next = new int[pattern.length()];
        if(pattern.length() <= 2){
            return next;
        }
        next[0] = 0; //第一个(第0位)总是 0
        next[1] = 0; //第二个总是 0
        int i = 2, j = 0;
        int loop = 0;
        while(i < next.length){
            loop++;
            if(pattern.charAt(i - 1) == pattern.charAt(j)){
                j++;

                // 如果要回溯到的位置的字符与当前字符相等
                if(pattern.charAt(j) == pattern.charAt(i)){
                    next[i] = next[j];
                }else{
                    next[i] = j;
                }
                i++;
            }else{
                if(j == 0){//表示只是比较第一个字符时就不相等时，i 需要往后移一位
                    i++;
                }
                j = 0;
            }
        }

        System.out.println("loop is: " + loop);

        printNext(next);

        return next;
    }

    private static void printNext(int[] next){
        //打印
        for(int i = 0 ; i < next.length; i++){
            System.out.print(next[i] + ", ");
        }
        System.out.println();
    }
}
